前言：最近快到FDS考试了，po重刷了一下学校的题目，自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦，所以在此共享一下我的题目和自己写的解题思路，欢迎各位指出错误~全章节预计会陆续更新，可在专栏查看~

HW2

1. For a sequentially stored linear list of length N, the time complexities for deleting the first element and inserting the last element are O(1) and O(N), respectively.

F 顺序表查找数据很快，时间复杂度为O(1)，但是插入的话需要把后续元素都往后移动，时间复杂度为O(N)。链表刚好相反。

2. If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive.

F 如果线性表用链式结构来存储，那元素地址必须连续存放。（错误，链表的结点每个都会存下一个结点地址，所以链表不需要连续存放）

3. To delete p from a doubly linked list, we must do:

A.p->prior=p->prior->prior; p->prior->next=p;

B.p->next->prior=p; p->next=p->next->next;

C.p->prior->next=p->next; p->next->prior=p->prior;

D.p->next=p->prior->prior; p->prior=p->next->next;

C 画图可知，p前一个结点的next要指向p后一个结点；p后一个结点的prior要指向p前一个结点。

4. If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then which of the following data structures is the most efficient?

A.doubly linked list

B.singly linked circular list

C.doubly linked circular list with a dummy head node

D.sequential list

D 因为插入删除元素只需要在尾部做，所以其实不会发生顺序存储时，插入新元素导致后续元素都要往后挪位置的情况。这样用顺序存储做插入删除和读取元素的时间复杂度都是O（1），所以省时间。

5.To merge two singly linked ascending lists, both with N nodes, into one singly linked ascending list, the minimum possible number of comparisons is:

A.1

B.N

C.2N

D.NlogN

B 要把两个有序单链表合并为一个链表，最少的比较情况可以假设一个链表中的元素是1,2,3,4,5；另一个链表是6,7,8,9,10；此时只要把6一直和1~5比5次就行，等前一个链表空了，再把后一个链表中的值直接链到新链表。所以最少比较N次。